#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
    TreeNode *tree = NULL;
    TreeNode *build(vector<int> &preorder, int pl, int pr, vector<int> inorder, int il, int ir)
    {
        if (pl > pr)
            return NULL;
        TreeNode *root = new TreeNode(preorder[pl]);
        int index = il;
        for (index = il; index <= ir; ++index)
        {
            if (inorder[index] == preorder[pl])
                break;
        }
        TreeNode *lchild = NULL, *rchild = NULL;
        lchild = build(preorder, pl + 1, pl + (index - il), inorder, il, index - 1);
        rchild = build(preorder, pl + (index - il) + 1, pr, inorder, index + 1, ir);
        root->left = lchild;
        root->right = rchild;
        return root;
    }
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
    {
        int len = preorder.size() - 1;
        tree = build(preorder, 0, len, inorder, 0, len);
        return tree;
    }
};
int main()
{
    vector<int> preorder = {3, 9, 20, 15, 7};
    vector<int> inorder = {9, 3, 15, 20, 7};
    Solution solver;
    solver.buildTree(preorder, inorder);
    return 0;
}